Hilbert Projection Theorem

Let HH be a Hilbert space ( inner product space that is complete with respect to the norm induced by the inner product) and MM be a finite dimensioal subspace of HH. Then for any xHx \in H, there exists a unique yMy \in M such that

minmMxm\min_{m \in M} \|x-m\|

has a unique solution yy. In other words "we can find a unique point in MM that is closest to xx". If mm^* is the closest point to xx in MM, then xmMx-m^* \perp M.

Proof: See lecture notes.

Remark: The proof stated that m=x1m^* = x_1 is the closest point to MM. It can also be interpreted as the best approximation of xx choosen from the vectors in MM. The x2x_2 term is the error in the approximation.


Example: Let V=R2V=\mathbb{R}^2 and M=span{[1,1]T}M = \text{span}\{[1,1]^T\}. Find the best approximation of x=[4,7]Tx=[4,7]^T in MM.

Solution: We need to find mm^* such that m=α[11]m^* = \alpha \begin{bmatrix} 1 \\ 1 \end{bmatrix} and xm\|x-m^*\| is minimum.

(xm)M    <xm,m>=0mM(x-m^*) \perp M \implies <x-m^*, m> = 0 \quad \forall m \in M
<xm,[11]>=0<x-m^*, \begin{bmatrix} 1 \\ 1 \end{bmatrix}> = 0
Replace x and m with their values.\text{Replace $x$ and $m^*$ with their values.}
<[4α7α],[11]>=0<\begin{bmatrix} 4-\alpha \\ 7-\alpha \end{bmatrix}, \begin{bmatrix} 1 \\ 1 \end{bmatrix}> = 0
Recall that <x,y>=xTy.\text{Recall that $1lt;x,y> = x^Ty$.}
4α+7α=04-\alpha + 7-\alpha = 0
α=112\alpha = \frac{11}{2}
m=112[11]m^* = \frac{11}{2} \begin{bmatrix} 1 \\ 1 \end{bmatrix}

Example: Let xVx \in V and M=span{v1,v2}M = \text{span}\{v_1, v_2\}. Find the best approximation of xx in MM.

Solution: We need to find mm^* such that m=α1v1+α2v2m^* = \alpha_1 v_1 + \alpha_2 v_2 that is in the span of MM and xm\|x-m^*\| is minimum.

(xm)M    (xm)both v1 and v2(x-m^*) \perp M \implies (x-m^*) \perp \text{both } v_1 \text{ and }v_2
<xα1v1α2v2,v1>=<x,v1>α1<v1,v1>α2<v2,v1>=0<x-\alpha_1 v_1 - \alpha_2 v_2, v_1> = <x, v_1> - \alpha_1 <v_1, v_1> - \alpha_2 <v_2, v_1> = 0
<xα1v1α2v2,v2>=<x,v2>α1<v1,v2>α2<v2,v2>=0<x-\alpha_1 v_1 - \alpha_2 v_2, v_2> = <x, v_2> - \alpha_1 <v_1, v_2> - \alpha_2 <v_2, v_2> = 0
[<v1,v1><v2,v1><v1,v2><v2,v2>][α1α2]=[<x,v1><x,v2>]\begin{bmatrix} <v_1, v_1> & <v_2, v_1> \\ <v_1, v_2> & <v_2, v_2> \end{bmatrix} \begin{bmatrix} \alpha_1 \\ \alpha_2 \end{bmatrix} = \begin{bmatrix} <x, v_1> \\ <x, v_2> \end{bmatrix}
[α1α2]=[<v1,v1><v2,v1><v1,v2><v2,v2>]1[<x,v1><x,v2>]\begin{bmatrix} \alpha_1 \\ \alpha_2 \end{bmatrix} = \begin{bmatrix} <v_1, v_1> & <v_2, v_1> \\ <v_1, v_2> & <v_2, v_2> \end{bmatrix}^{-1} \begin{bmatrix} <x, v_1> \\ <x, v_2> \end{bmatrix}
m=α1v1+α2v2m^* = \alpha_1 v_1 + \alpha_2 v_2

Example: Let V=R3V = \mathbb{R}^3 and M=span{[1,1,1]T,[1,0,1]T}M = \text{span}\{[1,1,1]^T, [1,0,1]^T\}. Find the best approximation of x=[4,7,2]Tx=[4,7,2]^T in MM.

Solution: We need to find mm^* such that m=α1[111]+α2[101]m^* = \alpha_1 \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} + \alpha_2 \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix} that is in the span of MM and xm\|x-m^*\| is minimum.

(xm)M    (xm)both v1 and v2(x-m^*) \perp M \implies (x-m^*) \perp \text{both } v_1 \text{ and }v_2
[<v1,v1><v2,v1><v1,v2><v2,v2>][α1α2]=[<x,v1><x,v2>]\begin{bmatrix} <v_1, v_1> & <v_2, v_1> \\ <v_1, v_2> & <v_2, v_2> \end{bmatrix} \begin{bmatrix} \alpha_1 \\ \alpha_2 \end{bmatrix} = \begin{bmatrix} <x, v_1> \\ <x, v_2> \end{bmatrix}
Recall that <x,y>=xTy.\text{Recall that $1lt;x,y> = x^Ty$.}
[3222][α1α2]=[136]\begin{bmatrix} 3 & 2 \\ 2 & 2 \end{bmatrix} \begin{bmatrix} \alpha_1 \\ \alpha_2 \end{bmatrix} = \begin{bmatrix} 13 \\ 6 \end{bmatrix}
[α1α2]=[3222]1[136]\begin{bmatrix} \alpha_1 \\ \alpha_2 \end{bmatrix} = \begin{bmatrix} 3 & 2 \\ 2 & 2 \end{bmatrix}^{-1} \begin{bmatrix} 13 \\ 6 \end{bmatrix}
[α1α2]=[1113/2][136]\begin{bmatrix} \alpha_1 \\ \alpha_2 \end{bmatrix} = \begin{bmatrix} 1 & -1 \\ -1 & 3/2 \end{bmatrix} \begin{bmatrix} 13 \\ 6 \end{bmatrix}
[α1α2]=[74]\begin{bmatrix} \alpha_1 \\ \alpha_2 \end{bmatrix} = \begin{bmatrix} 7 \\ -4 \end{bmatrix}
m=α1v1+α2v2=7[111]4[101]=[373]m^* = \alpha_1 v_1 + \alpha_2 v_2 = 7 \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} - 4 \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix} = \begin{bmatrix} 3 \\ 7 \\ 3 \end{bmatrix}

Example: Let HH be the space of square integrable functions on [π,π][-\pi , \pi ] with inner product <f,g>=ππf(t)g(t)ˉdt<f,g> = \int_{-\pi}^{\pi} f(t)\bar{g(t)}dt. Let MM be the subspace of HH, M=span{ejkt/2π}M = \text{span}\{e^{jkt}/\sqrt{2\pi}\}, k from N to Nk \text{ from } -N \text{ to } N. Note that dimension of MM is 2N+12N+1.

<fn,fm>=ππejnt2πejmt2πdt=12πππej(nm)tdt<f_n, f_m> = \int_{-\pi}^{\pi} \frac{e^{jnt}}{\sqrt{2\pi}} \frac{e^{-jmt}}{\sqrt{2\pi}} dt = \frac{1}{2\pi} \int_{-\pi}^{\pi} e^{j(n-m)t} dt
If nm, then 12πππej(nm)tdt=12πej(nm)tj(nm)ππ=0\text{If $n \neq m$, then } \frac{1}{2\pi} \int_{-\pi}^{\pi} e^{j(n-m)t} dt = \frac{1}{2\pi} \frac{e^{j(n-m)t}}{j(n-m)} \Big|_{-\pi}^{\pi} = 0
If n=m, then 12πππej(nm)tdt=12πππ1dt=1\text{If $n = m$, then } \frac{1}{2\pi} \int_{-\pi}^{\pi} e^{j(n-m)t} dt = \frac{1}{2\pi} \int_{-\pi}^{\pi} 1 dt = 1
Therefore, <fn,fm>={1if n=m0if nm\text{Therefore, } <f_n, f_m> = \begin{cases} 1 & \text{if $n = m$} \\ 0 & \text{if $n \neq m$} \end{cases}

Now, let gHg \in H be an arbitrary function. Then g=g1+g2g = g_1 + g_2 where g1Mg_1 \in M and g2Mg_2 \in M^{\perp}. We need to find g1g_1 such that gg1\|g-g_1\| is minimum.

g1=k=NNαkejkt2π where αk=<g,fk>=ππg(t)ejkt2πdt g_1 = \sum_{k=-N}^{N} \alpha_k \frac{e^{jkt}}{\sqrt{2\pi}} \text{ where } \alpha_k = <g, f_k> = \int_{-\pi}^{\pi} g(t) \frac{e^{-jkt}}{\sqrt{2\pi}} dt
αk=ππg(t)ejkt2πdt \alpha_k = \int_{-\pi}^{\pi} g(t) \frac{e^{-jkt}}{\sqrt{2\pi}} dt
g1=k=NNππg(t)ejkt2πejkt2πdt=k=NNππg(t)12πdt=ππg(t)dt g_1 = \sum_{k=-N}^{N} \int_{-\pi}^{\pi} g(t) \frac{e^{-jkt}}{\sqrt{2\pi}} \frac{e^{jkt}}{\sqrt{2\pi}} dt = \sum_{k=-N}^{N} \int_{-\pi}^{\pi} g(t) \frac{1}{2\pi} dt = \int_{-\pi}^{\pi} g(t) dt

Example: Find the orthagonal projection of the vector [100]\begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} onto the subspace M=span{[111],[111]}M = \text{span}\{\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}, \begin{bmatrix} 1 \\ -1 \\ 1 \end{bmatrix}\}.

Solution: We know that the projection matrix is P=B(BTB)1BTP = B(B^TB)^{-1}B^T where BB is the matrix whose columns are the basis vectors of MM. Therefore,

B=[111111]B = \begin{bmatrix} 1 & 1 \\ 1 & -1 \\ 1 & 1 \end{bmatrix}
BTB=[3113]B^TB = \begin{bmatrix} 3 & 1 \\ 1 & 3 \end{bmatrix}
P=[111111][3113]1[111111]P = \begin{bmatrix} 1 & 1 \\ 1 & -1 \\ 1 & 1 \end{bmatrix} \begin{bmatrix} 3 & 1 \\ 1 & 3 \end{bmatrix}^{-1} \begin{bmatrix} 1 & 1 & 1 \\ 1 & -1 & 1 \end{bmatrix}
P=[111111][3/81/81/83/8][111111]P = \begin{bmatrix} 1 & 1 \\ 1 & -1 \\ 1 & 1 \end{bmatrix} \begin{bmatrix} 3/8 & -1/8 \\ -1/8 & 3/8 \end{bmatrix} \begin{bmatrix} 1 & 1 & 1 \\ 1 & -1 & 1 \end{bmatrix}
P=[1/201/20101/201/2]P = \begin{bmatrix} 1/2 & 0 & 1/2 \\ 0 & 1 & 0 \\ 1/2 & 0 & 1/2 \end{bmatrix}
P[100]=[1/201/2]P \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} = \begin{bmatrix} 1/2 \\ 0 \\ 1/2 \end{bmatrix}

Solution of Linear Equations

Consider the linear equation expressed as

Ax=b where ACm×n,xCn,bCmAx = b \text{ where } A \in \mathbb{C}^{m \times n}, x \in \mathbb{C}^n, b \in \mathbb{C}^m

If m=nm = n, then the equation has a unique solution. If m<nm < n, then the equation has infinitely many solutions. If m>nm > n, then the equation has no solution.


Example: Let A=[1111]A = \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} and b=[2.21.92.11.8]b = \begin{bmatrix} 2.2 \\ 1.9 \\ 2.1 \\ 1.8 \end{bmatrix}. Find xx such that Ax=bAx = b.

Solution:

b?range(A) b \in^{?} \text{range}(A)
range(A)=span{[1,1,1,1]T}\text{range}(A) = \text{span}\{[1,1,1,1]^T\}
span{[1,1,1,1]T}={[a,a,a,a]TaR}\text{span}\{[1,1,1,1]^T\} = \{[a,a,a,a]^T \mid a \in \mathbb{R}\}
brange(A)b \notin \text{range}(A)

Therefore, there is no exact solution. We need to find the best approximation of bb in range(A)\text{range}(A).

Lets call this best approximation bb^*. Then, b=α[1111]b^* = \alpha \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} and Axb2\|Ax-b^*\|^2 is minimum.

B=[1111]B = \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix}
P=[1111][4]1[1111]P = \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} \begin{bmatrix} 4 \end{bmatrix}^{-1} \begin{bmatrix} 1 & 1 & 1 & 1 \end{bmatrix}
Pb=[1111][4]1[1111][2.21.92.11.8]Pb = \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} \begin{bmatrix} 4 \end{bmatrix}^{-1} \begin{bmatrix} 1 & 1 & 1 & 1 \end{bmatrix} \begin{bmatrix} 2.2 \\ 1.9 \\ 2.1 \\ 1.8 \end{bmatrix}
Pb=b=[2.02.02.02.0]Pb = b^* = \begin{bmatrix} 2.0 \\ 2.0 \\ 2.0 \\ 2.0 \end{bmatrix}

Example: Let A=[21212121]A = \begin{bmatrix} 2 & 1 \\ 2 & 1 \\ 2 & 1 \\ 2 & 1 \end{bmatrix} and b=[l1l2l3l4]b = \begin{bmatrix} l_1 \\ l_2 \\ l_3 \\ l_4 \end{bmatrix}. Find xx such that Ax=bAx = b.

Solution: Now, the rows of AA are linearly dependent. Therefore, AA is not full column rank. Therefore, there is no exact solution. We need to find the best approximation of bb in range(A)\text{range}(A).

b=[lˉlˉlˉlˉ] where lˉ=l1+l2+l3+l44b^* = \begin{bmatrix} \bar l \\ \bar l \\ \bar l \\ \bar l \end{bmatrix} \text{ where } \bar l = \frac{l_1+l_2+l_3+l_4}{4}
[21212121][x1x2]=[lˉlˉlˉlˉ]\begin{bmatrix} 2 & 1 \\ 2 & 1 \\ 2 & 1 \\ 2 & 1 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix}\bar l \\ \bar l \\ \bar l \\ \bar l \end{bmatrix}
[x1x2]=[lˉlˉ] is any solution, more examples [11],[23],[35],\begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix} \bar l \\ - \bar l \end{bmatrix} \text{ is any solution, more examples } \begin{bmatrix} 1 \\ -1 \end{bmatrix}, \begin{bmatrix} 2 \\ -3 \end{bmatrix}, \begin{bmatrix} 3 \\ -5 \end{bmatrix}, \ldots
A minimum norm solution is can be found by minimizing the norm of x.\text{A minimum norm solution is can be found by minimizing the norm of $x$.}
 For that, we can project any solution onto the null space perpendicular to A.\text{ For that, we can project any solution onto the null space perpendicular to $A$.}
x1=ProjN(A)[lˉlˉ]x_1 = \text{Proj}_{N(A)^{\perp}} \begin{bmatrix} \bar l \\ - \bar l \end{bmatrix}
Corollary: N(A)=range(A)\text{Corollary: } N(A)^{\perp} = \text{range}(A^*)
A=[22221111]A^* = \begin{bmatrix} 2 & 2 & 2 & 2 \\ 1 & 1 & 1 & 1 \end{bmatrix}
range(A)=span{[21]}\text{range}(A^*) = \text{span}\bigg \{\begin{bmatrix} 2 \\ 1 \end{bmatrix}\bigg\}
ProjN(A)[lˉlˉ]=Projrange(A)[lˉlˉ]\text{Proj}_{N(A)^{\perp}} \begin{bmatrix} \bar l \\ - \bar l \end{bmatrix} = \text{Proj}_{\text{range}(A^*)} \begin{bmatrix} \bar l \\ - \bar l \end{bmatrix}
Projrange(A)[lˉlˉ]=<[lˉlˉ],[21]><[21],[21]>[21]\text{Proj}_{\text{range}(A^*)} \begin{bmatrix} \bar l \\ - \bar l \end{bmatrix} = \frac{<\begin{bmatrix} \bar l \\ - \bar l \end{bmatrix}, \begin{bmatrix} 2 \\ 1 \end{bmatrix}>}{<\begin{bmatrix} 2 \\ 1 \end{bmatrix}, \begin{bmatrix} 2 \\ 1 \end{bmatrix}>} \begin{bmatrix} 2 \\ 1 \end{bmatrix}
Projrange(A)[lˉlˉ]=lˉ5[21]\text{Proj}_{\text{range}(A^*)} \begin{bmatrix} \bar l \\ - \bar l \end{bmatrix} = \frac{\bar l}{5} \begin{bmatrix} 2 \\ 1 \end{bmatrix}
 Or in projection matrix form, Q=[21] then, P=Q(QQ)1Q\text{ Or in projection matrix form, } Q = \begin{bmatrix} 2 \\ 1 \end{bmatrix} \text{ then, } P = Q(Q^*Q)^{-1}Q^*
P=[21]15[21]=[4/52/52/51/5]P = \begin{bmatrix} 2 \\ 1 \end{bmatrix} \frac{1}{5} \begin{bmatrix} 2 & 1 \end{bmatrix} = \begin{bmatrix} 4/5 & 2/5 \\ 2/5 & 1/5 \end{bmatrix}
x1=Px=[4/52/52/51/5][lˉlˉ]=[4/5lˉ2/5lˉ2/5lˉ1/5lˉ]=[2/5lˉ1/5lˉ]=lˉ/5[21]x_1 = Px = \begin{bmatrix} 4/5 & 2/5 \\ 2/5 & 1/5 \end{bmatrix} \begin{bmatrix} \bar l \\ - \bar l \end{bmatrix} = \begin{bmatrix} 4/5 \bar l - 2/5 \bar l \\ 2/5 \bar l - 1/5 \bar l \end{bmatrix} = \begin{bmatrix} 2/5 \bar l \\ 1/5 \bar l \end{bmatrix} = \bar l/ 5 \begin{bmatrix} 2 \\ 1 \end{bmatrix}

Special Cases of Ax=bAx = b

1.1 Columns of AA are linearly independent

If the columns of AA are linearly independent, then AA is full rank and ATAA^TA is invertible. Therefore, x=(ATA)1ATbx = (A^TA)^{-1}A^Tb is the unique solution.

AA is full column rank with AA is m×nm \times n and mnm \geq n if and only if N(A)={0}N(A) = \{0\}. (Tall matrix)

If brange(A)b \in \text{range}(A), then the solution exists and is unique. If bR(A)b \notin \text{R}(A), then the solution does not exist.

Ax=ProjR(A)bAx = \text{Proj}_{\text{R}(A)}b is the best approximation of bb in R(A)\text{R}(A).

P=A(ATA)1ATP = A(A^TA)^{-1}A^T is the projection matrix onto R(A)\text{R}(A).

Ax=A(ATA)1ATbAx = A(A^TA)^{-1}A^Tb is the best approximation of bb in R(A)\text{R}(A).

AxA(ATA)1ATb=0Ax - A(A^TA)^{-1}A^Tb = 0 since the projection of bb onto R(A)\text{R}(A).

A(x(ATA)1ATb)=0A(x - (A^TA)^{-1}A^Tb) = 0

x(ATA)1ATbN(A)x - (A^TA)^{-1}A^Tb \in N(A) and the null space contains only the zero vector.

x=(ATA)1ATbx = (A^TA)^{-1}A^Tb is the unique solution.

1.2 Columns of AA are linearly dependent

If the columns of AA are linearly dependent, then AA is not full rank and ATAA^TA is not invertible. Therefore, x=(ATA)1ATbx = (A^TA)^{-1}A^Tb is not the unique solution.

2.1 Rows of AA are linearly independent

If the rows of AA are linearly independent, then AA is full row rank and AATAA^T is invertible. Therefore, x=AT(AAT)1bx = A^T(AA^T)^{-1}b is the unique solution.

AA is full row rank with AA is m×nm \times n and mnm \leq n if and only if N(AT)={0}N(A^T) = \{0\}. (Wide matrix)

If brange(A)b \in \text{range}(A), then the solution exists and is unique. If bR(A)b \notin \text{R}(A), then the solution does not exist.

dim(R(A))=dim(R(AT))=rank(A)=rank(AT)    bR(A)\text{dim}(\text{R}(A)) = \text{dim}(\text{R}(A^T)) = \text{rank}(A) = \text{rank}(A^T) \implies b \in \text{R}(A)

For a minimum norm solution, we need to project bb onto the null space perpendicular to AA.

x=ProjN(A)b=ProjR(A)bx = \text{Proj}_{N(A)^{\perp}}b = \text{Proj}_{\text{R}(A^*)}b

P=A(AA)1A=A(AA)1AP = A^*(AA^*)^{-1}A = A^*(A^*A)^{-1}A

Px=A(AA)1Ax=A(AA)1bPx = A^*(AA^*)^{-1}Ax = A^*(AA^*)^{-1}b

2.2 Rows of AA are linearly dependent

If the rows of AA are linearly dependent, then AA is not full row rank and AATAA^T is not invertible. Therefore, x=AT(AAT)1bx = A^T(AA^T)^{-1}b is not the unique solution.

3.1 AA is square and invertible

If AA is square and invertible, then x=A1bx = A^{-1}b is the unique solution.


Example: Let A=[111123321]A = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 2 & 3 \\ 3 & 2 & 1 \end{bmatrix} and b=[121]b = \begin{bmatrix} 1 \\ 2 \\ -1 \end{bmatrix}. Find xx such that Ax=bAx = b.

Solution:

First, we need to check if brange(A)b \in \text{range}(A). Since AA has linearly dependent columns

range(A)=span{[113],[131]}\text{range}(A) = \text{span}\bigg\{\begin{bmatrix} 1 \\ 1 \\ 3 \end{bmatrix}, \begin{bmatrix} 1 \\ 3 \\ 1 \end{bmatrix}\bigg\}
dim(range(A))=rank(A)=2\text{dim}(\text{range}(A)) = \text{rank}(A) = 2
dim(N(A))=nrank(A)=32=1\text{dim}(N(A)) = n - \text{rank}(A) = 3 - 2 = 1
N(A)=span{[121]}N(A) = \text{span}\bigg\{\begin{bmatrix} 1 \\ 2 \\ -1 \end{bmatrix}\bigg\}
brange(A)b \notin \text{range}(A)

Therefore, there is no exact solution. We need to find the best approximation of bb in range(A)\text{range}(A).

B=[111331]B = \begin{bmatrix} 1 & 1 \\ 1 & 3 \\ 3 & 1 \end{bmatrix}
P=B(BTB)1BTP = B(B^TB)^{-1}B^T
P=[111331][117711]1[113131]P = \begin{bmatrix} 1 & 1 \\ 1 & 3 \\ 3 & 1 \end{bmatrix} \begin{bmatrix} 11 & 7 \\ 7 & 11 \end{bmatrix}^{-1} \begin{bmatrix} 1 & 1 & 3 \\ 1 & 3 & 1 \end{bmatrix}
P=172[111331][117711][113131]P = \frac{1}{72} \begin{bmatrix} 1 & 1 \\ 1 & 3 \\ 3 & 1 \end{bmatrix} \begin{bmatrix} 11 & -7 \\ -7 & 11 \end{bmatrix} \begin{bmatrix} 1 & 1 & 3 \\ 1 & 3 & 1 \end{bmatrix}
P=172[111331][4102642610]P = \frac{1}{72} \begin{bmatrix} 1 & 1 \\ 1 & 3 \\ 3 & 1 \end{bmatrix} \begin{bmatrix} 4 & -10 & 26 \\ 4 & 26 & -10 \end{bmatrix}
P=172[816161668416468]P = \frac{1}{72} \begin{bmatrix} 8 & 16 & 16 \\ 16 & 68 & -4 \\ 16 & -4 & 68 \end{bmatrix}
Pb=172[816161668416468][121]=[1/313/65/6]Pb = \frac{1}{72} \begin{bmatrix} 8 & 16 & 16 \\ 16 & 68 & -4 \\ 16 & -4 & 68 \end{bmatrix} \begin{bmatrix} 1 \\ 2 \\ -1 \end{bmatrix} = \begin{bmatrix} 1/3 \\ 13/6 \\ -5/6 \end{bmatrix}
b=Pb=[1/313/65/6]b^* = Pb = \begin{bmatrix} 1/3 \\ 13/6 \\ -5/6 \end{bmatrix}

Now, the problem has a solution. However for the uniqueness, we need to check if AA is full row rank. Since AA has linearly dependent rows, AA is not full row rank. Therefore, the solution is not unique, hence we need to find the minimum norm solution. For that, we need to project bb onto the null space perpendicular to AA.

Starting with any solution xx,

x=[x1x2x3]x = \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix}
Let x1=0\text{Let } x_1 = 0
[111123321][0x2x3]=[1/313/65/6]\begin{bmatrix} 1 & 1 & 1 \\ 1 & 2 & 3 \\ 3 & 2 & 1 \end{bmatrix} \begin{bmatrix} 0 \\x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix} 1/3 \\ 13/6 \\ -5/6 \end{bmatrix}
x2=76 and x3=96x_2 = \frac{-7}{6} \text{ and } x_3 = \frac{9}{6}
x=[07/69/6]x = \begin{bmatrix} 0 \\ -7/6 \\ 9/6 \end{bmatrix}
Now, xmin is the projection of x onto the null space perpendicular to A.\text{Now, $x_{min}$ is the projection of $x$ onto the null space perpendicular to $A$.}
xmin=ProjN(A)x=ProjR(A)xx_{min} = \text{Proj}_{N(A)^{\perp}}x = \text{Proj}_{\text{R}(A^*)}x
A=[113122131]A^* = \begin{bmatrix} 1 & 1 & 3 \\ 1 & 2 & 2 \\ 1 & 3 & 1 \end{bmatrix}
range(A)=span{[111],[123]}\text{range}(A^*) = \text{span}\bigg\{\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}, \begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix}\bigg\}
Q=[111213]Q = \begin{bmatrix} 1 & 1 \\ 1 & 2 \\ 1 & 3 \end{bmatrix}
P=Q(QQ)1QP = Q(Q^*Q)^{-1}Q^*
P=[111213][36614]1[111123]P = \begin{bmatrix} 1 & 1 \\ 1 & 2 \\ 1 & 3 \end{bmatrix} \begin{bmatrix} 3 & 6 \\ 6 & 14 \end{bmatrix}^{-1} \begin{bmatrix} 1 & 1 & 1 \\ 1 & 2 & 3 \end{bmatrix}
P=16[521222125]P = \frac{1}{6} \begin{bmatrix} 5 & 2 & -1 \\ 2 & 2 & 2 \\ -1 & 2 & 5 \end{bmatrix}
xmin=Px=16[521222125][07/69/6]=[25/364/3631/36]x_{min} = Px = \frac{1}{6} \begin{bmatrix} 5 & 2 & -1 \\ 2 & 2 & 2 \\ -1 & 2 & 5 \end{bmatrix} \begin{bmatrix} 0 \\ -7/6 \\ 9/6 \end{bmatrix} = \begin{bmatrix} -25/36 \\ 4/36 \\ 31/36 \end{bmatrix}

#EE501 - Linear Systems Theory at METU